The present invention relates to performing authentication as to whether or not an element possesses a pre-specified property. An example is authenticating validity of a digital revocation in a public key infrastructure, or authenticating validity of an entitlement to use a resource (e.g. to sign onto a World Wide Web site).
FIG. 1 illustrates digital certificate validation and revocation in a public key infrastructure. Digital certificates 104 are used in public key infrastructures (PKI) to facilitate secure use and management of public keys in a networked computer environment. Users U1, U2, . . . utilize their computer systems 110.1, 110.2, . . . to generate respective key pairs (PK, SK) where PK is the public key and SK is the secret key. FIG. 1 shows a key pair (PKU1, SKU1) for user U1. The users register their public keys PK, over a network, with a certification authority (CA) 120. Alternatively, the key pairs can be generated by CA 120 and sent to the users. CA 120 is a secure, trusted computer system. For each public key PK, CA 120 generates a digital certificate 104. Certificate 104 contains the public key PK and the user's name and/or email address or addresses, may also contain the certificate's serial number SN (generated by the CA to simplify the certificate management), the certificate issue date D1, the expiration date D2, an identification of algorithms to be used with the public and secret keys, an identification of the CA 120, and possibly other data. The data mentioned above is shown at 104D. Certificate 104 also contains CA's signature 104-SigCA on the data 104D. The signature is generated using CA's secret key SKCA. CA 120 sends the certificate 104 to the user's (key owner's) computer system 110. Either the owner or the CA 120 can distribute the certificate to other parties to inform them of the user's public key PK. Such parties can verify the CA's signature 104-SigCA with the CA's public key PKCA to ascertain that the certificate's public key PK does indeed belong to the person whose name and email address are provided in the certificate.
A certificate may have to be revoked prior to its expiration date D2. For example, the certificate owner U may change his affiliation or position, or the owner's private key SKU may be compromised. Other parties must be prevented from using the owner's public key if the certificate is revoked.
One approach to prevent the use of public keys of revoked certificates is through a certificate revocation list (CRL). A CRL is a signed and time-stamped list issued by CA 120 and specifying the revoked certificates by their serial numbers SN. These CRLs must be distributed periodically even if there are no new revoked certificates in order to prevent any type of replay attack. The CRL management may be unwieldy with respect to communication, search, and verification costs. The CRL approach can be optimized using so-called delta-CRLs, with the CA transmitting only the list of certificates that have been revoked in the previous time period (rather than for all time periods). The delta-CRL technique still has the disadvantage that the computational complexity of verifying that a certificate is currently valid is basically proportional to the number of time periods, since the verifier must confirm that the certificate is not in any of the delta-CRLs.
Certificate revocation trees (CRTs) can be used instead of CRLs as described in [15] (the bracketed numbers indicate references listed at the end before the claims).
Instead of CRLs and CRTs, CA 120 could answer queries about specific certificates. In FIG. 1, user U2 issues a query 150 with the serial number SN of certificate 104 of user U1. CA 120 responds with a validity status information 160 containing the serial number SN, a validity status field 160VS (“valid”, “revoked” or “unknown”), and a time stamp “Time”. The response is signed by CA (field 160-SigCA). This approach is used for Online Certificate Status Protocol (OCSP). See [23]. Disadvantageously, the CA's digital signature 160-SigCA can be quite long (over 1024 bits with RSA), especially since the CA must be very secure. In addition, if CA 120 is centralized, the CA becomes a validation bottleneck. If CA 120 is decentralized (replicated), the security is weakened as the CA's signing key SKCA is replicated.
FIG. 2 illustrates a “NOVOMODO” approach, which allows CA 120 to provide an unsigned validity status through untrusted directories 210 at pre-specified time intervals (e.g. every day, or every hour, etc.). Directories 210 are computer systems that do not store secret information. The system works as follows.
Let f be a predefined public length-preserving functionf:{0,1}n→{0,1}n where {0,1}n is the set of all binary strings of a length n. Let fi denote the f-fold composition; that is, fi(x)=x for i=0, and fi(x)=f(fi−1(x)) for i>0. Let f be one-way, i.e. given f(x) where x is randomly chosen, it is hard (infeasible) to find a pre-image z such that f(z)=f(x), except with negligible probability. “Infeasible” means that given a security parameter k (e.g. k=n), the pre-image z cannot be computed in a time equal to a predefined polynomial in k except with negligible probability. Let us assume moreover that f is one-way on its iterates, i.e. for any i, given y=fi(x), it is infeasible to find z such that f(z)=y.
We can assume, without loss of generality, that CA is required to provide a fresh validity status every day, and the certificates are valid for one year, i.e. 365 days (D2−D1=365 days). To create a certificate 104 (FIG. 2), CA 120 picks a random “seed” number x and generates a “hash chain” c0, c1, . . . c365 wherein:c365=f(x), c364=f(f(x)), . . . c1=f365(x), c0=f366(x).  (1)We will sometimes denote x as x(SN) for a certificate with a serial number SN, and similarly ci=ci(SN) where i=0, 1, . . . . The value c0 is called a “validation target”. CA 120 inserts c0 into the certificate 104 together with data 104D (FIG. 1). CA 120 also generates a random revocation seed number N0, computes the “revocation target” N1=f(N0), and inserts N1 into certificate 104. CA 120 keeps all ci secret for i>0. The values x and N0 are also secret. Clearly, all ci can all be computed from x, and the validation target c0 can be computed from any ci. CA 120 stores in its private storage the values x and N0 for each certificate 104, and possibly (but not necessarily) caches the ci values.
Every day i (i=1, 2, . . . 365), a certificate re-validation is performed for the valid certificates as follows. For each certificate 104, CA distributes to directories 210 a validation data structure which includes, in addition to a validity status indication (not shown in FIG. 2, can be “valid” or “revoked”):    1. the certificate's “i-token” ci if the certificate is valid on day i;    2. the revocation seed N0 if the certificate has been revoked.(We will call ci a “validity proof”, and N0 a “revocation proof”.) This information is distributed unsigned. Each directory 210 provides this information, unsigned, to a requester system 110 in response to a validity status request 150 (FIG. 1). To verify, the requester (verifier) 110 performs the following operations:    1. If the validity status is “valid”, the verifier 110 checks that fi(ci)=c0.    2. If the validity status is “revoked”, the verifier 110 checks that f(N0)=N1.Despite the validity information being unsigned, the scheme is secure because given ci, it is infeasible to compute the subsequent tokens ci+1, ci+2, . . . .
To reduce the communication between CA 120 and directories 210, a hash chain (1) can be generated for a set of certificates 104, and a single i-token ci can be distributed for the set if the set is “unrevoked” (i.e. all the certificates are unrevoked in the set). The certificate 140 will contain a separate target c0 for each set containing the certificate and associated with a hash chain (see [1]).
Certificate revocation can also be performed using accumulators. See [37]. An accumulator is a way to combine a set of values (e.g. a set of valid certificates) into a shorter value. A formal definition of a “secure” accumulator is given in Appendix A at the end of this disclosure before the claims. An accumulator example can be constructed as follows. Let us denote all possible values that can be accumulated as p1, . . . , pt. (For example, each pi can be a unique number assigned to a certificate, and we want to accumulate the values corresponding to the valid certificates.) Suppose v0 is the accumulator value for the empty set. Let ƒ be a one-way function. To accumulate p1, we compute the accumulator as follows:v({p1})=f(v0,p1)  (2)Now to accumulate p2, we set the accumulator to be v2=ƒ(v1,p2), and so on. More generally, the accumulator value for some set {pi1, . . . pim} isv({pi1, . . . , pim})=ƒ(ƒ( . . . ƒ(v0, pi1) . . . ), pim)  (3)The function ƒ can be chosen such that the accumulation order does not matter, i.e.ƒ(ƒ(v,pi),pi)=ƒ(ƒ(v,pi),pi)  (4)(this is the “quasi-commutative” property).
In each period j, CA 120 can send to the directories 210 a pair (vj,t) where vj is the accumulator value for the set of the valid certificates, and t is a time stamp. The directories can respond to queries 150 with some proof that the accumulator value vj accumulates the value pi corresponding to the certificate of interest.
A common accumulator is an RSA accumulator defined as follows:ƒ(v,p)=vp mod n  (5)where p is a positive integer, and n=q1q2 is the product of large prime numbers q1 and q2. In this case,
                              v          ⁡                      (                          {                                                p                                      i                    1                                                  ,                …                ⁢                                                                  ,                                  p                                      i                    m                                                              }                        )                          =                                            v              0                                                                        p                                      i                    1                                                  ,                …                ⁢                                                                  ,                                  p                                      i                    m                                                              ⁢                                                                            ⁢          mod          ⁢                                          ⁢          n                                    (        6        )            
The certificate validation is performed as follows. Without loss of generality, suppose that the values p1, . . . , pm correspond to the valid certificates in a period j. Then the accumulator value distributed by CA 120 to directories 210 isvj=v0p1 . . . pm mod n  (7)If a verifier 110 inquires a directory 210 of the status of a certificate corresponding to the value pi which is one of p1, . . . , pm the directory sends to the verifier the accumulator value vj and a “witness” valuesi,j=v0p1 . . . pi−1pi+1 . . . pm mod n  (8)The verifier checks thatsi,jpi=vj mod n  (9)If this equality holds, the certificate is assumed to be valid.
The witness si,j is hard to forge provided that it is hard to compute the pi-th root of vj. The pi-th root computation is hard if the adversary does not know the factorization of n and the strong RSA assumption is valid (this assumption is defined in Appendix A). However, it is possible to keep pi and si,j secret. For example, instead of providing the values si,j and pi to the verifier, the verifier can be provided with a proof that such values exist and are known to the certificate owner.
Accumulators can be used more generally to prove that an element satisfies some pre-specified property.